package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 *
 * https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/description
 *
 * ```
 * 1161. 最大层内元素和
 * 给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
 * 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
 *
 * 示例 1：
 * 输入：root = [1,7,0,7,-8,null,null]
 * 输出：2
 * 解释：
 * 第 1 层各元素之和为 1，
 * 第 2 层各元素之和为 7 + 0 = 7，
 * 第 3 层各元素之和为 7 + -8 = -1，
 * 所以我们返回第 2 层的层号，它的层内元素之和最大。
 *
 * 示例 2：
 * 输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
 * 输出：2
 *
 *
 * 提示：
 * 树中的节点数在 [1, 104]范围内
 * -105 <= Node.val <= 105
 *
 * ```
 */
class leetcode_1161 {
    @Test
    fun test_1() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n7 = TreeNode(7)
        val n7_2 = TreeNode(7)
        val n8 = TreeNode(-8)
        val root = n1

        n1.left = n7
        n1.right = n0

        n7.left = n7_2
        n7.right = n8

        val actual = maxLevelSum(root)
        val expected = 2
        Assert.assertEquals(expected, actual)
    }

    fun maxLevelSum(root: TreeNode?): Int {
        /**
        题型： 二叉树的层级遍历
        思路：
        计算每层的sum，当sum > 全局 maxSum 时，更新 maxSum = sum，层数 level = 本层 count
        最后返回 level
         */
        // 1 确定终止条件
        if (null == root) {
            return 0
        }

        var level: Int = 0
        var maxSum: Int = Int.MIN_VALUE
        var levelCount: Int = 0

        // 2 队列初始化
        val queue: LinkedList<TreeNode> = LinkedList()
        queue.offer(root)

        // 3 外层：判断是否结束
        while (!queue.isEmpty()) {
            // 本层的元素个数
            var size = queue.size
            var sum: Int = 0
            levelCount++
            // 4 内层：本层的层级级遍历
            while (size-- > 0) {
                val node: TreeNode = queue.poll()
                sum = sum + node.`val`
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
            // 5 收集本层数据
            if (sum > maxSum) {
                maxSum = sum
                level = levelCount
            }
        }
        return level
    }
}